/*
 * @lc app=leetcode.cn id=312 lang=golang
 *
 * [312] 戳气球
 */

// @lc code=start

func maxCoins(nums []int) int {
	n := len(nums)
	val := make([]int, 0, n+2)
	val = append(val, 1)
	for _, v := range nums {
		val = append(val, v)
	}
	val = append(val, 1)
	res := make([][]int, 0, n+2)
	for i := 0; i < n+2; i++ {
		res = append(res, make([]int, n+2))
	}
	// 使用自底向上的动态规划方式
	// 因为涉及三个端点，因此我们固定最左端
	//使另两端遍历，找寻最大的值
	for i := n - 1; i >= 0; i-- {
		for j := i + 2; j < n+2; j++ {
			for k := i + 1; k < j; k++ {
				num := val[k] * val[i] * val[j]
				num += res[i][k] + res[k][j]
				res[i][j] = max(num, res[i][j])
			}
		}
	}
	return res[0][n+1]

}
func max(i, j int) int {
	if i < j {
		return j
	}
	return i
}

// @lc code=end
